Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління Звіт до лабораторної роботи №3 Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ).  ЛАБОРАТОРНА РОБОТА №3 Тема: Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ). Мета: Навчитися працювати з ДПФ та ШПФ. Теоретичні відомості: Дискретне перетворення Фур(є (ДПФ): ДПФ - це перетворення Фур(є послідовності кінцевої довжини, що є сама по собі також послідовністю, а не перервною функцією і відповідає рівновіддаленим за частотою вибіркам перетворення Фур(є-сигнала. ДПФ – вводиться як :
,
де х(nT) (n=0,…, N-1)- послідовність з N-часових відліків з періодом T; X(k)- послідовність (k=0,…,N-1) з N-частотних відліків;
. Формула (3.1) - пряме ДПФ. Формула (3.2) - обернене ДПФ. ДПФ у матричній формі:
, (3.3) де X і x – N-вимірні вектори, X=[X(0),X(1),…,X(N-1)]T, х=[x(0),x(T),…,x((N-1)Т)]T; WN-матриця розміром N*N з елементами d(n,k), n,k-індекси за рядком, за стовпчиком d(n,k)=WNnk ; n,k=0,1,2,…N-1. Формула (3.1) - пряме ДПФ у матричній формі. Обернена форма формули: x=WN-1X, (3.4) де WN-1 - обернена матриця до матриці WN, тобто її елемент; d-1(n,k)=1/N*WN-nk . ДПФ вводиться для представлення як періодичних послідовностей з періодом N-відліків, так і послідовності кінцевої довжини N. Коефіцієнти ДПФ кінцевої послідовності дорівнюють значенням її у z-перетворенні у N-точках рівномірно розподілених по одиничному колу. Формула одиничного кола:
, де к-0,1,2,…N-1. ДПФ виконується над кінцевою послідовністю N-відліків або над періодичною послідовністю, період якої складається також з N-відліків. Оскільки характеристики спектра послідовностей таких як спектральна густина потужності, амплітуди, фази окремих частот на практиці визначають з використанням тільки кінцевого числа відліків. Звідси випливає, що ДПФ є одним з найважливіших засобів їх визначення. Властивості ДПФ: 1.Властивість лінійності.
(3.5) 2.Зсув ДПФ. Нехай
, а y(nT) отримується з x(nT) шляхом зсуву на n0 відліків.
(3.6)
, (3.7) де K0-зсув спектра. 3.Властивість симетрії Якщо послідовність x(nT) є дійсною то її ДПФ задовольняє таким умовам симетрії: Дійсна частина: Re(X(k))=Re(X(N-k)) Уявна частина: Im(X(k))= -Im(X(N-k))
(3.8) Наслідки від властивостей ДПФ: 1) ДПФ симетричної послідовності буде дійсною, тобто Якщо x (nT)= x ((N-n)T) ( Im (Х(k))=0 2.) Властивість симетрії дозволяє за допомогою одного ДПФ перетворити одночасно дві дійсних послідовності. Якщо
ДПФ то
Тоді:
(3.9) 4) Згортка по колу. Нехай уU(nT) є згорткою по колу сигналів x (nT) и y(nT) а)
, тоді її ДПФ
б) Якщо
то її ДПФ також є згорткою
5.) Спряжена форма обернення. Обернене ДПФ за формулою (3.2) можна обчислити за допомогою формул для прямого ДПФ.
, де
- комплексне спряження від p
(3.10) Алгоритми швидких перетворень Фур(є (ШПФ): Обчислення ДПФ потребує великої кількості операцій (формула 3.1): приблизно N2 додавань і N2 добутків. Якщо розглянути для реальних частин (розпишемо комплекс через уявну і дійсну частини), то операцій буде в 4 рази більше.
Отримуємо 4N2 операцій множення, додавання трохи менше. Так як кількість обчислень, а значить і час обчислення пропорційне N2, то при прямому методі обчислень ДПФ число арифметичних операцій різко зростає зі збільшенням N, тому були розроблені алгоритми, що зменшують число операцій, які називаються ШПФ. Найчастіше застосовується :
;
- натуральне число(оптимальний випадок для БПФ. Основна ідея, що лежить в основі усіх ШПФ, полягає в зведенні N-точкового ШПФ до обчислення декількох N1-точечних ДПФ, при чому N1<<N. Існує два великих ділення. Алгоритми, при реалізації яких потрібна перестановка відліків x(nT) вхідної послідовності, називаються алгоритмами з проріджуванням за часом....